Halftoning is a technique that is commonly used in digital imaging to create the appearance of intermediate tones when only two colorant levels (i.e., ink or no ink) are available. Halftoning methods rely on the fact that an observer's eye will spatially average over some local area of the image so that intermediate tone levels can be created by turning some of the pixels "on" and some of the pixels "off" in some small region. The fraction of the pixels which are turned on will determine the apparent tone level. Examples of common halftoning techniques include ordered dither and error-diffusion.
Ordered dither techniques are implemented by storing either a set of dither bitmaps for a series of tone levels, or a threshold matrix that can be used to produce a set of halftone patterns. A wide variety of halftone patterns can be formed in this manner depending on the values stored in the dither bitmaps, or the threshold matrix. Common types of halftone patterns include random dither matrices, clustered-dot dither matrices, and Bayer (dispersed dot) dither matrices.
Sullivan and Miller (U.S. Pat. No. 4,920,501) have recently introduced a technique to design dither bitmaps which have minimum visual modulation. These patterns are sometimes called "blue-noise" patterns. They are desirable in that the patterns that are produced have minimum visibility to human observers, and as a result are visually pleasing relative to other patterns. The basic procedure involved in the creation of these patterns is to use an optimization technique, such as simulated annealing, to determine the arrangement of the dots in the halftone pattern that minimizes some visual cost function. One class of visual cost functions is based upon weighting the frequency components of the halftone patterns with a human visual sensitivity function.
The method of Sullivan and Miller can be implemented using the process shown in FIG. 1. In this case a set of dither bitmaps 12 are used corresponding to the halftone patterns determined for each tone level k. A given pixel in the image has column and row addresses x and y, respectively, and an input pixel value I(x,y). The input pixel value is the code value associated with a particular tone level. For each x-y pixel location in the image, the input pixel value I(x,y) is used to select which of the dither bitmaps should be used for that pixel. Modulo operators 10 are used to determine indices x.sub.d and y.sub.d that are used to address the selected dither bitmap to determine the output pixel value O(x,y).
For the method described by Sullivan and Miller, the halftone patterns for each tone level are derived independently, and are therefore uncorrelated. This is acceptable for image areas that contain only a single tone level. However, for image regions that contain smooth gradients from one tone level to another, undesirable artifacts occur at the transitions between the tone levels. These artifacts manifest themselves as an increased image graininess which enhances the visibility of the halftone patterns. To eliminate this problem, Sullivan and Ray (U.S. Pat. No. 5,214,517) have disclosed an enhancement to this basic method that insures that the bitmaps for each of the tone levels are correlated with each other. By "correlated" it is meant that once a certain pixel in the dither bitmap is turned on (e.g. set to print black) at a certain input pixel value, it will remain the same, i.e. turned on, in the dither bit maps for all darker input pixel values. This effectively eliminates the undesirable artifacts at the transitions between the tone levels. Other extensions to this basic approach include a method for simultaneously optimizing the bit maps for all of the tone levels (see U.S. application Ser. No. 07/848,779, filed by L. A. Ray); a method for designing blue-noise dither matrices for use with multi-level output devices (see U.S. Pat. No. 5,586,203, issued Dec. 17, 1996 to Spaulding et al.), and a method for jointly designing dither matrices for each color channel of a color image (see U.S. application Ser. No. 08/658,452 by Spaulding et al.).
The correlated halftone patterns can be implemented using the same dither bitmap method that was shown in FIG. 1. Alternatively, Granger et al. (U.S. Pat. No. 4,918,622) have shown that a threshold matrix approach can also be used interchangeably with the dither bitmap so long as the patterns are correlated. In this case, the threshold matrix indicates the tone level at which each pixel turns on. A flow chart for this approach is shown in FIG. 2. A given pixel in the image has column and row addresses x and y, respectively, and an input pixel value I(x,y). Modulo operators 20 are used to determine indices x.sub.d and y.sub.d that are used to address the dither matrix 22. The threshold value d(x.sub.d,y.sub.d) stored in the dither matrix at this address is then compared to the input pixel value I(x,y) using a comparator 24. If the input pixel value is below the threshold value, the output pixel value O(x,y) is set to "off"; if the value is above the threshold, the output pixel value O(x,y) is set to "on".
Another implementation of this basic technique is shown in FIG. 3. In this case the threshold value d(x.sub.d,y.sub.d) is combined with the input pixel value I(x,y) using an adder 34. A threshold operator 36 is then used to threshold the combined value to determine the output pixel value O(x,y).
It should be noted that any dither pattern which can be implemented using the methods of FIG. 2 and FIG. 3 can also be implemented using the method of FIG. 1. However, it is possible to define a set of dither bitmaps for the method of FIG. 1 that could not be implemented using the other methods. This is because in the dither matrix implementations once a certain pixel is turned on at the input pixel value corresponding to the threshold, it will stay on for all higher input pixel values. With the dither bitmaps approach this constraint is not present. For example, a certain pixel could be "off" for an input pixel value of 150, "on" for an input pixel value of 151, and "off" again for an input pixel value of 152. In other words the dither bitmap approach can produce either correlated or uncorrelated halftone patterns, whereas the dither matrix approaches can only produce correlated halftone patterns.
Parker and Mitsa (U.S. Pat. No. 5,111,310), Lin (U.S. Pat. Nos. 5,317,418 and 5,469,515) and Barton, (European patent application 0 647 058 A2, application date Apr. 5, 1995) have also recently introduced techniques for the design of dither patterns. Although the actual optimization methods that they have used is somewhat different, the resulting patterns are quite similar to those created using the methods described in the Sullivan et al. patents.
As discussed above, the use of correlated blue-noise halftone patterns eliminates the noise artifacts that occur on the boundaries between different tone levels when uncorrelated blue-noise halftone patterns are used. However, the halftone pattern generated for any single tone level will generally be somewhat less optimal than that produced with uncorrelated bitmaps. This is a result of the fact that once a dot is turned "on" for one tone level, it must be left on for all higher tone levels. Thus this provides many fewer degrees of freedom in the halftone pattern optimization process. There is a need therefore for a halftoning method that eliminates the noise artifacts on the boundaries between different tone levels, without imposing the quality compromise associated with the correlated dot pattern solution.